package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.*;

/**
 * 113. 路径总和 II
 * 广度优先搜索
 *
 * 使用哈希表记录树中的每一个节点的父节点。
 * 每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，
 * 即可还原出从根节点到当前节点的路径
 *
 * @author fy
 * @date 2022/4/24 21:27
 */
public class Solution113_4 {

    private List<List<Integer>> res = new ArrayList<>();
    private Map<TreeNode, TreeNode> map = new HashMap<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return res;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> valQueue = new LinkedList<>();
        nodeQueue.offer(root);
        valQueue.offer(targetSum - root.val);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int val = valQueue.poll();
            if (node.left == null && node.right == null) {
                if (val == 0) {
                    res.add(getPath(node));
                }
                continue;
            }
            if (node.left != null) {
                nodeQueue.offer(node.left);
                valQueue.offer(val - node.left.val);
                map.put(node.left, node);
            }
            if (node.right != null) {
                nodeQueue.offer(node.right);
                valQueue.offer(val - node.right.val);
                map.put(node.right, node);
            }
        }
        return res;
    }

    private List<Integer> getPath(TreeNode node) {
        List<Integer> list = new ArrayList<>();
        while (node != null) {
            list.add(0, node.val);
            node = map.get(node);
        }
        return list;
    }

}
